//全排列
/*给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同*/
class Solution {
    vector<vector<int>> arr;
    vector<int> path;
    bool check[7] = {0};

public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return arr;
    }
    void dfs(vector<int>& nums) {
        if (path.size() == nums.size()) {
            arr.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (check[i] == false) {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};



//二叉树的所有路径
/*给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。
树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100
*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
    vector<string> arr;

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        string s;
        dfs(root, s);
        return arr;
    }
    void dfs(TreeNode* root, string s) {
        if (root == nullptr)
            return;
        s += to_string(root->val);
        if (root->left == nullptr && root->right == nullptr) {
            arr.push_back(s);
            return;
        }
        s += "->";
        dfs(root->left, s);
        dfs(root->right, s);
    }
};

//子集
/*给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
*/
class Solution {
    vector<vector<int>> arr;
    vector<int> path;
    int i = 0;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, i);
        return arr;
    }

    void dfs(vector<int>& nums, int i) {
        if (i == nums.size()) {
            arr.push_back(path);
            return;
        }
        dfs(nums, i + 1);
        path.push_back(nums[i]);
        dfs(nums, i + 1);
        path.pop_back();
    }
};

// 找出所有子集的异或总和再求和
/*一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。

例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

注意：在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

 1 <= nums.length <= 12
1 <= nums[i] <= 20*/
class Solution {
    int k = 0;
    int sum = 0;

public:
    int subsetXORSum(vector<int>& nums) {
        dfs(nums, 0);
        return sum;
    }
    void dfs(vector<int>& nums, int pos) {
        sum += k;
        cout<<sum<<"-";
        cout<<k<<" ";
        for (int i = pos; i < nums.size(); i++) {
            k ^= nums[i];
            dfs(nums, i + 1);
            k ^= nums[i];
        }
    }
};